package leetcode.editor.cn;//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
//
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
//一个节点也可以是它自己的祖先）。” 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
//输出：3
//解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
// 
//
// 示例 2： 
//
// 
//输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
//输出：5
//解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], p = 1, q = 2
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [2, 105] 内。 
// -109 <= Node.val <= 109 
// 所有 Node.val 互不相同 。 
// p != q 
// p 和 q 均存在于给定的二叉树中。 
// 
// Related Topics 树 深度优先搜索 二叉树 
// 👍 1433 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class leetcode.editor.cn.TreeNode {
 *     int val;
 *     leetcode.editor.cn.TreeNode left;
 *     leetcode.editor.cn.TreeNode right;
 *     leetcode.editor.cn.TreeNode(int x) { val = x; }
 * }
 */
class Solution236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //v为k的父结点
        Map<TreeNode,TreeNode> parentNode=new HashMap<>();
        Deque<TreeNode> stack=new ArrayDeque<>();
        stack.push(root);
        TreeNode tmp;
        boolean p1=false,q1=false;
        while(!stack.isEmpty()){
            tmp=stack.pop();
            TreeNode lc = tmp.left;
            TreeNode rc = tmp.right;
            if(lc !=null){
                parentNode.put(lc,tmp);
                stack.push(lc);
            }
            if(rc !=null){
                parentNode.put(rc,tmp);
                stack.push(rc);
            }
            if(lc==p||rc==p) p1=true;
            if(lc==q||rc==q) q1=true;
            if(p1&&q1) break;
        }
        //记录p及其祖先节点们
        Set<TreeNode> pParents=new HashSet<>();
        TreeNode parent;
        while(p!=null){
            pParents.add(p);
            p=parentNode.get(p);
        }
        //遍历q的祖父节点，比较有没有和pParents重复的
        while(q!=null){
            if(pParents.contains(q)) return q;
            q=parentNode.get(q);
        }
        return null;

    }
    /**
     * 1.p q分别在root的左右子树
     * 2.p q在root的一个子树上
     * 递归前序遍历树
     */
    public TreeNode lowestCommonAncestor01(TreeNode root, TreeNode p, TreeNode q) {
        //root为空，返回null说明p q不存在于这个以root为根的树种
        //root=p or q，说明找到了，返回找到的值
        if(root==null||p==root||q==root) return root;
        TreeNode lr = lowestCommonAncestor(root.left, p, q);
        TreeNode rr = lowestCommonAncestor(root.right, p, q);
        //左右子树都找到了pq，说明pq在root的左右两侧，root为最近祖先
        if(lr!=null&&rr!=null) return root;
        //左子树没找到porq，说明都在右子树，返回lr即可
        if(lr!=null) return lr;
        return rr;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
